#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n);
        if(s[0]!='0')
        {
            dp[0]=1;
        }
        if(n==1) 
            return dp[0];
        if(s[0]!='0' && s[1]!='0')
        {
            dp[1]+=1;
        }
        if((s[0]-'0')*10+s[1]-'0'>=10&& (s[0]-'0')*10+s[1]-'0'<=26 )
        {
            dp[1]+=1;
        }
        for(int i=2;i<n;i++)
        {
            int t1=0;
            if(s[i]>='1' && s[i]<='9')
            {
                t1 = dp[i-1];
            }
            int t2=0;
            if((s[i-1]-'0')*10+s[i]-'0'>=10 && (s[i-1]-'0')*10+s[i]-'0'<=26)
            {
                t2 = dp[i-2];
            }
            dp[i] = t1+t2;
        }
        return dp[n-1];
    }
};


class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=s[0]!='0';
        if(n==1) 
            return dp[1];
        for(int i=2;i<=n;i++)
        {
            int t1=0;
            if(s[i-1]>='1' && s[i-1]<='9')
            {
                t1 = dp[i-1];
            }
            int t2=0;
            if((s[i-2]-'0')*10+s[i-1]-'0'>=10 && (s[i-2]-'0')*10+s[i-1]-'0'<=26)
            {
                t2 = dp[i-2];
            }
            dp[i] = t1+t2;
        }
        return dp[n];
    }
};